{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum OR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #bit-manipulation #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #位运算 #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumOr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大或值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code> 。每一次操作中，你可以选择一个数并将它乘&nbsp;<code>2</code>&nbsp;。</p>\n",
    "\n",
    "<p>你最多可以进行 <code>k</code>&nbsp;次操作，请你返回<em>&nbsp;</em><code>nums[0] | nums[1] | ... | nums[n - 1]</code>&nbsp;的最大值。</p>\n",
    "\n",
    "<p><code>a | b</code>&nbsp;表示两个整数 <code>a</code>&nbsp;和 <code>b</code>&nbsp;的 <strong>按位或</strong>&nbsp;运算。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [12,9], k = 1\n",
    "<b>输出：</b>30\n",
    "<b>解释：</b>如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [8,1,2], k = 2\n",
    "<b>输出：</b>35\n",
    "<b>解释：</b>如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 15</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-or](https://leetcode.cn/problems/maximum-or/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-or](https://leetcode.cn/problems/maximum-or/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[12,9]\\n1', '[8,1,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        v, v2 = 0, 0\n",
    "        for x in nums:\n",
    "            v2 |= v & x\n",
    "            v |= x\n",
    "        m = max(nums)\n",
    "        if v2 == v and (v & (v + 1)) == 0:\n",
    "            return (m << k) | v\n",
    "        res = v\n",
    "        p = 1 << int(math.log2(m))\n",
    "        for x in nums:\n",
    "            if x >= p:\n",
    "                res = max(res, (x << k) | (x ^ v) | v2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\r\n",
    "        cnt = Counter()\r\n",
    "        res = 0 \r\n",
    "        for x in nums:\r\n",
    "            for i in range(32):\r\n",
    "                if x & (1 << i) != 0:\r\n",
    "                    cnt[i] += 1 \r\n",
    "        for x in nums:\r\n",
    "            y = 0 \r\n",
    "            for i in range(32):\r\n",
    "                if x & (1 << i) != 0:\r\n",
    "                    cnt[i] -= 1\r\n",
    "                    y |= (1 << (i + k))\r\n",
    "                if cnt[i]:\r\n",
    "                    y |= (1 << i)\r\n",
    "                if x & (1 << i) != 0:\r\n",
    "                    cnt[i] += 1 \r\n",
    "            res = max(res, y) \r\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        t = len(bin(nums[0])[2:])\n",
    "        # for i in range(len(nums)):\n",
    "        #     u = bin(nums[i])[2:]\n",
    "        #     u = '0'*(t-len(u))+u\n",
    "        #     print(u)\n",
    "        \n",
    "\n",
    "        count = [0]*(t+k)\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            u = bin(nums[i])[2:]\n",
    "            u = '0'*(t+k-len(u))+u\n",
    "            for j in range(len(u)):\n",
    "                if u[j] == '1':\n",
    "                    count[j] += 1\n",
    "\n",
    "\n",
    "        m = 0\n",
    "        c = copy.deepcopy(count)\n",
    "        for i in range(len(nums)):\n",
    "            now = bin(nums[i])[2:]\n",
    "            if len(now) < t:\n",
    "                break\n",
    "            now = '0'*(t+k-len(now))+now\n",
    "            # print(now,c)\n",
    "            count = copy.deepcopy(c)\n",
    "            for j in range(k,len(count)):\n",
    "                if now[j] == '1':\n",
    "                    count[j-k] += 1\n",
    "                    count[j] -= 1\n",
    "            ans = ''\n",
    "            # print(count)\n",
    "            for i in range(len(count)):\n",
    "                if count[i]>=1:\n",
    "                    ans += '1'\n",
    "                else:\n",
    "                    ans += '0'\n",
    "            m = max(m,int(ans,2))\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        dct, N, res = defaultdict(int), 0, 0\n",
    "\n",
    "        for n in nums:\n",
    "            N |= n\n",
    "\n",
    "            i = 0\n",
    "            while n:\n",
    "                if n & 1:\n",
    "                    dct[i] += 1\n",
    "                n >>= 1\n",
    "                i += 1\n",
    "\n",
    "        #print(N, bin(N)[2:], dct)\n",
    "        for n in nums:\n",
    "            #print(n, '-----')\n",
    "            val = N\n",
    "            i, t = 0, n\n",
    "            while t:\n",
    "                if (t & 1) and dct[i] == 1:\n",
    "                    #print('i:  ',i)\n",
    "                    val ^= 1 << i\n",
    "                t >>= 1\n",
    "                i += 1   \n",
    "\n",
    "            #print(n, n << k, bin(n)[2:], bin(n<<k)[2:], 'val: ', val)\n",
    "\n",
    "            res = max(res, val | (n << k))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0] * (n + 1)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i] | nums[i]\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            s = pre[i] | (nums[i] * (2 ** k)) | suf[i + 1]\n",
    "            ans = max(ans, s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "\n",
    "        numsList = [0 for _ in range(N+1)]\n",
    "        \n",
    "        for i in range(N-1, -1, -1):\n",
    "            numsList[i] = numsList[i+1] | nums[i]  # 逐个与找最大\n",
    "        \n",
    "        pre=ans=0\n",
    "        for i,x in enumerate(nums):\n",
    "            ans = max(ans, pre | (nums[i] << k) | numsList[i+1])  # 遍历各个数移k次的情况\n",
    "            pre|=x \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "\n",
    "        numsList = [0 for _ in range(N+1)]\n",
    "        \n",
    "        for i in range(N-1, -1, -1):\n",
    "            numsList[i] = numsList[i+1] | nums[i]  # 逐个与找最大\n",
    "        \n",
    "        pre=ans=0\n",
    "        for i,x in enumerate(nums):\n",
    "            ans = max(ans, pre | (nums[i] << k) | numsList[i+1])  # 遍历各个数移k次的情况\n",
    "            pre|=x \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        surf=[0 for i in range(n+1)]\n",
    "        #求后缀和\n",
    "        for i in range(n-1, 0, -1):\n",
    "            surf[i]=surf[i+1]|nums[i]\n",
    "        pre=0\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            temp = pre | (nums[i]<<k) | surf[i+1]\n",
    "            pre|=nums[i]\n",
    "            ans=max(ans, temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        suf=[0]*(n+1)\n",
    "        for i in range (0,n):\n",
    "            suf[n-i-1]=suf[n-i]|nums[n-1-i]\n",
    "\n",
    "        ans=0\n",
    "        tem=0\n",
    "        for i in range (0,n):\n",
    "            ans=max(ans,(nums[i]<<k)|suf[i+1]|tem)\n",
    "            tem=tem|nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        pre = ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, pre | nums[i] << k | suf[i + 1])\n",
    "            pre |= nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        suf=[0] * (n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suf[i]=suf[i+1] | nums[i]\n",
    "        ans=0\n",
    "        pre=0\n",
    "        for i,x in enumerate(nums):\n",
    "            \n",
    "            ans=max(ans,pre|x<<k|suf[i+1])\n",
    "            pre=pre|nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suffix = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1 , -1):\n",
    "            suffix[i] = suffix[i+1] | nums[i] \n",
    "        ans = pre = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            ans = max(ans, pre | (v << k) | suffix[i+1])\n",
    "            pre |= v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        # suffix[i] 代表i+1及之后的进行或操作\n",
    "        n = len(nums)\n",
    "        suffix = [0] * n\n",
    "        for i in range(n-2, -1, -1):\n",
    "            suffix[i] = suffix[i+1] | nums[i+1]\n",
    "        \n",
    "        ans, pre = 0, 0\n",
    "        for i, num in enumerate(nums):\n",
    "            temp = pre | (num << k)\n",
    "            ans = max(ans, temp | suffix[i])\n",
    "            pre |= num\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        suf=[0] * (n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suf[i]=suf[i+1] | nums[i]\n",
    "        ans=0\n",
    "        pre=0\n",
    "        for i,x in enumerate(nums):\n",
    "            \n",
    "            ans=max(ans,pre|x*2**k|suf[i+1])\n",
    "            pre=pre|nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n+1)\n",
    "        for i in range(n-1, 0, -1):\n",
    "            suf[i] = suf[i+1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i+1])\n",
    "            pre |= x\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        num=[0]*(n+1)\n",
    "        pre=0\n",
    "        maxend=0\n",
    "        for i in range(n-1,0,-1):\n",
    "            num[i]=num[i+1]|nums[i]\n",
    "        for i,x in enumerate(nums):\n",
    "            maxend=max(maxend,pre|(x<<k)|num[i+1])\n",
    "            pre=pre|nums[i]\n",
    "        return maxend"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        suffix = [0] * (len(nums) + 1)\n",
    "\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            suffix[i] = suffix[i + 1] | nums[i]\n",
    "        \n",
    "        prefix = 0\n",
    "        res = float('-inf')\n",
    "        for i in range(len(nums)):\n",
    "            res = max(res, prefix | (nums[i] << k) | suffix[i + 1])\n",
    "            prefix |= nums[i]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        #贪心+前后缀分解\n",
    "        n=len(nums)\n",
    "        suf=[0]*n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            suf[i]=nums[i+1]|suf[i+1]\n",
    "        pre=ans=0\n",
    "        for i in range(n):\n",
    "            cur=nums[i]<<k\n",
    "            ans=max(ans,pre|cur|suf[i])\n",
    "            pre|=nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        p=[0]*(n+1)\n",
    "        for i in range(n-1,0,-1):\n",
    "            p[i]=p[i+1]|nums[i]\n",
    "        ans=temp=0\n",
    "        for i in range(n):\n",
    "            ans=max(ans,temp|nums[i]<<k|p[i+1])\n",
    "            temp|=nums[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        suf = [0] * (n + 1)\n",
    "\n",
    "        for i in range(n - 1, 0, -1):\n",
    "\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "\n",
    "        ans = pre = 0\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "\n",
    "            pre |= x\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0]*(n+1)\n",
    "        for i in range(n-1,0,-1):\n",
    "            suf[i] = nums[i] | suf[i+1]\n",
    "        \n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            \n",
    "            knum = nums[i]<<k \n",
    "            ans = max(ans, pre|knum|suf[i+1])\n",
    "            pre = pre|nums[i]\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        suf=[0]*(n+1)\n",
    "        # suf[-1]=nums[-1]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suf[i]=suf[i+1]|nums[i]\n",
    "        pre=0\n",
    "        ans=-1\n",
    "        for i in range(n):\n",
    "            ans=max(ans,pre|(nums[i]*2**k)|suf[i+1])\n",
    "            pre|=nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        mx = 0\n",
    "        res = -1\n",
    "        ans = 0\n",
    "        cnt = [0] * 32\n",
    "        for x in nums:\n",
    "            for i in range(32):\n",
    "                if (x >> i) & 1: cnt[i] += 1\n",
    "        print(cnt)\n",
    "        for x in nums:\n",
    "            z = 0\n",
    "            for i in range(32):\n",
    "                if (x >> i) & 1: \n",
    "                    cnt[i] -= 1\n",
    "                if cnt[i]: z += (1 << i)\n",
    "            y = x << k\n",
    "            if res != -1 and z != 0: \n",
    "                ans = max(ans, res | y | z)\n",
    "                res |= x\n",
    "            elif res == -1:\n",
    "                ans = max(ans, y | z)\n",
    "                res = x\n",
    "            else:\n",
    "                ans = max(ans, res | y)\n",
    "                res |= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "    l = len(nums)\n",
    "    o = [0] * (l + 1)\n",
    "    for i in range(l):\n",
    "      v = nums[i]\n",
    "      o[i] = o[i - 1] | v\n",
    "    r = 0\n",
    "    ret = 0\n",
    "    for i in range(l - 1, -1, -1):\n",
    "      v = nums[i]\n",
    "      if i + 1 < l:\n",
    "        r |= nums[i + 1]\n",
    "      \n",
    "      v <<= k\n",
    "      ret = max(o[i - 1] | r | v, ret)\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        suf=[0]*(n+1)\n",
    "        # suf[-1]=nums[-1]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suf[i]=suf[i+1]|nums[i]\n",
    "        pre=0\n",
    "        ans=-1\n",
    "        for i in range(n):\n",
    "            ans=max(ans,pre|(nums[i]<<k)|suf[i+1])\n",
    "            pre|=nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, a: List[int], v: int) -> int:\n",
    "        n=len(a)\n",
    "        b=[0]*35\n",
    "        for i in a:\n",
    "            for j,k in enumerate(f\"{i:b}\"[::-1]):\n",
    "                if k=='1':\n",
    "                    b[j]+=1\n",
    "        ans=0\n",
    "        for i in a:\n",
    "            c=[i for i in b]\n",
    "            for j,k in enumerate(f\"{i:b}\"[::-1]):\n",
    "                if k=='1':\n",
    "                    c[j]-=1\n",
    "            c=int(''.join('1' if j>0 else '0' for i,j in enumerate(c))[::-1],2)\n",
    "            ans=max(ans,(i<<v)|c)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suffixs = [0] * (n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suffixs[i] = nums[i] | suffixs[i+1]\n",
    "\n",
    "        pre = ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, pre | (nums[i]<<k) | suffixs[i+1])\n",
    "            pre |= nums[i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n-1, 0, -1):\n",
    "            suf[i] = suf[i+1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k )| suf[i+1])\n",
    "            pre |= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        s = 0\n",
    "        prefix = [0] * len(nums) \n",
    "        for i, x in enumerate(nums):\n",
    "            s |= x\n",
    "            prefix[i] = s\n",
    "        prefix = [0] + prefix\n",
    "        res = 0\n",
    "        s = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            x = nums[i]\n",
    "            res = max(res, prefix[i] | s | (x << k))\n",
    "            s |= x\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0]*(n+1)\n",
    "\n",
    "        for i in range(n-1,0,-1):\n",
    "            suf[i] = suf[i+1] | nums[i]\n",
    "\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans,pre | (x<<k)| suf[i+1])\n",
    "            pre |=x\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        res, ans = 0, 0\n",
    "        for i, x in enumerate(nums):\n",
    "            y = x << k\n",
    "            ans = max(ans, res | y | suf[i + 1])            \n",
    "            res |= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        suf=[0]*n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            suf[i]=nums[i+1]|suf[i+1]\n",
    "        pre=ans=0\n",
    "        for i in range(n):\n",
    "            cur=nums[i]<<k\n",
    "            ans=max(ans,pre|cur|suf[i])\n",
    "            pre|=nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        ans = pre = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre | (x << k) | suf[i + 1])\n",
    "            pre |= x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        suf=[0]*(n+1)\n",
    "        for i in range(n-1,0,-1):\n",
    "            suf[i]=suf[i+1]|nums[i]\n",
    "        res=pre=0\n",
    "        for i,x in enumerate(nums):\n",
    "            res=max(res,pre|(x<<k)|suf[i+1])\n",
    "            pre|=x\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\r\n",
    "        # cnt = Counter()\r\n",
    "        # res = 0 \r\n",
    "        # for x in nums:\r\n",
    "        #     for i in range(32):\r\n",
    "        #         if x & (1 << i) != 0:\r\n",
    "        #             cnt[i] += 1 \r\n",
    "        # for x in nums:\r\n",
    "        #     y = 0 \r\n",
    "        #     for i in range(32):\r\n",
    "        #         if x & (1 << i) != 0:\r\n",
    "        #             cnt[i] -= 1\r\n",
    "        #             y |= (1 << (i + k))\r\n",
    "        #         if cnt[i]:\r\n",
    "        #             y |= (1 << i)\r\n",
    "        #         if x & (1 << i) != 0:\r\n",
    "        #             cnt[i] += 1 \r\n",
    "        #     res = max(res, y) \r\n",
    "        # return res  \r\n",
    "        n = len(nums)\r\n",
    "        suf = [0] * (n + 1)\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            suf[i] = suf[i + 1] | nums[i]\r\n",
    "        pre = 0 \r\n",
    "        res = 0\r\n",
    "        for i, x in enumerate(nums):\r\n",
    "            res = max(res, pre | (x << k) | suf[i + 1])\r\n",
    "            pre |= x \r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        suffixs = [0] * (n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suffixs[i] = nums[i] | suffixs[i+1]\n",
    "\n",
    "        pre = ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, pre | (nums[i]<<k) | suffixs[i+1])\n",
    "            pre |= nums[i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        xop = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            xop[i+1] = xop[i] | nums[i]\n",
    "        xol = [0]*(n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            xol[i] = xol[i+1] | nums[i]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans,xop[i] | nums[i] << k | xol[i+1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] | nums[i]\n",
    "        \n",
    "        post = [0]*(n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            post[i] = post[i+1] | nums[i]\n",
    "        s = [num.bit_length() for num in nums]\n",
    "        ceil = max(s)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if ceil == s[i]:\n",
    "                cur = pre[i]|post[i+1]|(nums[i]<<k)\n",
    "                if cur > ans:\n",
    "                    ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        n=len(nums)\n",
    "        suf=[0]*(n+1)\n",
    "        for i in range(n-1,0,-1):\n",
    "            suf[i]=suf[i+1]|nums[i]\n",
    "        pre=[0]*(n+1)\n",
    "        for i in range(0,n):\n",
    "            pre[i+1]=pre[i]|nums[i]\n",
    "        \n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            ans = max(ans, pre[i] | (nums[i] << k) | suf[i + 1])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        preor=[0]*(n+1)\n",
    "        subor=[0]*(n+1)\n",
    "        preor[0]=nums[0]\n",
    "        subor[n-1]=nums[-1]\n",
    "        for i in range(1,n):\n",
    "            preor[i]=preor[i-1]|nums[i]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            subor[i]=subor[i+1]|nums[i]\n",
    "        l=[len(bin(num))-2 for num in nums]\n",
    "        maxl=max(l)\n",
    "        idx=l.index(maxl)\n",
    "        res=0\n",
    "        for i in range(idx,n):\n",
    "            res=max(res,preor[i-1]|subor[i+1]|(nums[i]<<k))\n",
    "        return res \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] | nums[i]\n",
    "        \n",
    "        post = [0]*(n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            post[i] = post[i+1] | nums[i]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            cur = pre[i]|post[i+1]|(nums[i]<<k)\n",
    "            if cur > ans:\n",
    "                ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0]\n",
    "        for i in range(1, n):\n",
    "            pre.append(nums[i - 1] | pre[-1])\n",
    "        sub = [0] * (n)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            sub[i] = nums[i + 1] | sub[i + 1]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, pre[i] | nums[i] << k | sub[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        # pre[i] : [0: i], suf[i] : [i: n - 1]\n",
    "        pre = [0] * (n + 1)\n",
    "        suf = [0] * (n + 1)\n",
    "        pre[0] = nums[0]\n",
    "        for i in range(n):\n",
    "            pre[i] = pre[i - 1] | nums[i]\n",
    "        suf[n - 1] = nums[-1]\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i]\n",
    "        # 枚举左移哪个\n",
    "        for i in range(n):\n",
    "            x = nums[i] << k\n",
    "            if i >= 1:\n",
    "                x |= pre[i - 1]\n",
    "            if i <= n - 2:\n",
    "                x |= suf[i + 1]\n",
    "            ans = max(ans, x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        # pre[i] : [0: i), suf[i] : (i: n - 1]\n",
    "        pre = [0] * (n + 1)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            pre[i] = pre[i - 1] | nums[i - 1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i + 1]\n",
    "        # 枚举左移哪个\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre[i] | ( x << k) | suf[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        N = len(nums)\n",
    "        pre = [0 for _ in range(N+1)]\n",
    "        for i in range(0, N):\n",
    "            pre[i+1] = pre[i] | nums[i]\n",
    "        print(pre)\n",
    "        suf = [0 for _ in range(N+1)]\n",
    "        for i in range(N-1, -1, -1):\n",
    "            suf[i] = suf[i+1] | nums[i]\n",
    "        print(suf)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(N):\n",
    "            ans = max(ans, pre[i] | (nums[i] << k) | suf[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        suf = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i] = pre[i-1] | nums[i-1]\n",
    "            suf[n-i]= suf[n-i+1] | nums[n-i]\n",
    "        max_res = 0\n",
    "        for i in range(n):\n",
    "            max_res = max(max_res, (nums[i]<<k)|(pre[i]|suf[i+1]))\n",
    "\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0] * (n + 1)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i-1] | nums[i-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            suf[i] = suf[i + 1] | nums[i + 1]\n",
    "        print(pre)\n",
    "        print(suf)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans = max(ans, pre[i] | suf[i] | x << k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        L = len(nums)\n",
    "        pre = [0]+nums[:]\n",
    "        suf = nums[:]+[0]\n",
    "        for i in range(1,L+1):\n",
    "            pre[i] = pre[i-1]|nums[i-1]\n",
    "            suf[-1-i] = suf[-i]|nums[-i]\n",
    "        \n",
    "        return max(pre[i]|suf[i+1]|n<<k for i,n in enumerate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, xs: List[int], k: int) -> int:\n",
    "        N = len(xs)\n",
    "\n",
    "        xorps = [0 for _ in range(N+1)]\n",
    "        for i in range(0, N, +1):\n",
    "            xorps[i+1] = xorps[i] | xs[i]\n",
    "        xorss = [0 for _ in range(N+1)]\n",
    "        for i in range(N-1, -1, -1):\n",
    "            xorss[i] = xorss[i+1] | xs[i]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(N):\n",
    "            ans = max(ans, xorps[i] | (xs[i] << k) | xorss[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        pre, post, N, res = [0], [0], len(nums), 0\n",
    "\n",
    "        for i in range(N):\n",
    "            pre.append(pre[-1] | nums[i])\n",
    "            post.append(post[-1] | nums[N - i - 1])\n",
    "\n",
    "        for i in range(N):\n",
    "            res = max(res, pre[i] | post[N - i - 1] | nums[i] << k)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        # 把k次操作都集中给最长位的数，直接枚举每个数，记录前缀或和后缀或，并将nums[i]<<k\n",
    "        n=len(nums)\n",
    "        if n==1:return nums[0]<<k\n",
    "        pre,suf=[0]*n,[0]*n\n",
    "        pre[0]=nums[0] \n",
    "        for i in range(1,n):\n",
    "            pre[i]=pre[i-1]|nums[i]\n",
    "        suf[n-1]=nums[n-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            suf[i]=suf[i+1]|nums[i]\n",
    "        # print(pre)\n",
    "        # print(suf)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                ans=max(ans,(nums[i]<<k)|suf[i+1])\n",
    "            elif i==n-1:\n",
    "                ans=max(ans,(nums[i]<<k)|pre[i-1])\n",
    "            else:\n",
    "                ans=max(ans,pre[i-1]|suf[i+1]|(nums[i]<<k))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        s1 = [0]*len(nums)\n",
    "        s2 = [0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            j = len(nums)-i-1\n",
    "            if i == 0:\n",
    "                s1[i] = nums[i]\n",
    "                s2[j] = nums[j]\n",
    "            else:\n",
    "                s1[i] = s1[i-1] | nums[i]\n",
    "                s2[j] = s2[j+1] | nums[j]\n",
    "        ans = 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]*2**k\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                ans = max(ans, s2[i+1] | (nums[i]*2**k))\n",
    "            elif i == len(nums)-1:\n",
    "                ans = max(ans, s1[i-1] | (nums[i]*2**k))\n",
    "            else:\n",
    "                ans = max(ans, s1[i-1] | s2[i+1] | (nums[i]*2**k))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        prefix = []\n",
    "        suffix = []\n",
    "\n",
    "        n = len(nums)\n",
    "        for index in range(n):\n",
    "            prefix.append(nums[index])\n",
    "            if index > 0:\n",
    "                prefix[-1] |= prefix[-2]\n",
    "        \n",
    "        for index in range(n - 1, -1, -1):\n",
    "            suffix.append(nums[index])\n",
    "            if index < n - 1:\n",
    "                suffix[-1] |= suffix[-2]\n",
    "        \n",
    "        suffix.reverse()\n",
    "\n",
    "        res = 0\n",
    "        for index in range(n):\n",
    "            v = nums[index] << k\n",
    "            if index > 0:\n",
    "                v |= prefix[index - 1]\n",
    "            if index < n - 1:\n",
    "                v |= suffix[index + 1]\n",
    "        \n",
    "            res = max(res, v)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        pre=[0 for  i in range(n)]\n",
    "        sub=[0 for  i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            pre[i]=pre[i-1]|nums[i-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            sub[i]=sub[i+1]|nums[i+1]\n",
    "        maxr=0\n",
    "        for i in range(n):\n",
    "            \n",
    "            csum = pre[i]|sub[i] | (nums[i] << k)\n",
    "            maxr=max(csum,maxr)\n",
    "        \n",
    "        return   maxr "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            t = nums[0]\n",
    "            for i in range(k):\n",
    "                t *= 2\n",
    "            return t\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        left[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            left[i] = left[i-1] | nums[i]\n",
    "        right[n-1] = nums[n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            right[i] = right[i+1] | nums[i]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            t = nums[i]\n",
    "            for j in range(k):\n",
    "                t *= 2\n",
    "            if i == 0:\n",
    "                ans = max(ans, t | right[i+1])\n",
    "            elif i == n - 1:\n",
    "                ans = max(ans, t | left[i-1])\n",
    "            else:\n",
    "                ans = max(ans, left[i-1] | t | right[i+1])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        pre, post, N, res = [0], [0], len(nums), 0\n",
    "\n",
    "        for i in range(N):\n",
    "            pre.append(pre[-1] | nums[i])\n",
    "            post.append(post[-1] | nums[N - i - 1])\n",
    "\n",
    "        for i in range(N):\n",
    "            res = max(res, pre[i] | post[N - i - 1] | nums[i] << k     )\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre, post = [0] * n, [0] * n\n",
    "        tmp = 0\n",
    "        for i in range(1, n):\n",
    "            tmp |= nums[i-1]\n",
    "            pre[i] = tmp\n",
    "        tmp = 0\n",
    "        for i in range(n-2, -1, -1):\n",
    "            tmp |= nums[i+1]\n",
    "            post[i] = tmp\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, pre[i]|(nums[i]<<k)|post[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = [0]*n\n",
    "        right = [0]*n\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                left[i] = 0\n",
    "                right[n-1-i] = 0\n",
    "            else:\n",
    "                left[i] = left[i-1] | nums[i-1]\n",
    "                right[n-1-i] = right[n-i]|nums[n-i]\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                result = max(result, 2**k*nums[0]|right[0])\n",
    "            elif i == n-1:\n",
    "                result = max(result, 2**k*nums[-1]|left[i])\n",
    "            else:\n",
    "                result = max(result, 2**k*nums[i]|left[i]|right[i])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        left = [0 for i in range(len(nums))]\n",
    "        right = [0 for i in range(len(nums))]\n",
    "        left[0], right[-1] = nums[0], nums[-1]\n",
    "        for i in range(1, len(nums)):\n",
    "            left[i] = left[i - 1] | nums[i]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            right[i] = right[i + 1] | nums[i]\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            r = right[i + 1] if i + 1 < len(nums) else 0\n",
    "            l = left[i - 1] if i - 1 >= 0 else 0\n",
    "            if (tmp := r | l | (nums[i] << k)) > ans:\n",
    "                ans = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        pre = 0\n",
    "        left = []\n",
    "        for i in range(n):\n",
    "            left.append(pre)\n",
    "            pre = pre | nums[i]\n",
    "        pre = 0\n",
    "        right = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            right.append(pre)\n",
    "            pre = pre | nums[i]\n",
    "        right = right[::-1]\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            result = max(result,left[i] | (nums[i]*2**k) | right[i])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\n",
    "        left,right = [],[]\n",
    "        pre = 0\n",
    "        for i in range(len(nums)):\n",
    "            pre = pre | nums[i]\n",
    "            left.append(pre)\n",
    "        pre = 0\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            pre = pre | nums[i]\n",
    "            right.append(pre)\n",
    "        right.reverse()\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            l = left[i-1] if i-1>=0 else 0\n",
    "            r = right[i+1] if i+1<len(nums) else 0\n",
    "            t = l|(nums[i]*(2**k))|r\n",
    "            res = max(res,t)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maximumOr(self, nums: List[int], k: int) -> int:\r\n",
    "        #[a,b,c,d]\r\n",
    "        #prefix: [0,a,a|b,a|b|c]\r\n",
    "        #suffix: [b|c|d,c|d,d,0]\r\n",
    "        #ans = max(prefix[i] | suffix[i] | (nums[i] << k))\r\n",
    "        n = len(nums)\r\n",
    "        pre = [0] * n\r\n",
    "        suf = [0] * n\r\n",
    "        for i in range(1,n):\r\n",
    "            pre[i] = pre[i-1] | nums[i-1]\r\n",
    "        for i in range(n-2, -1, -1):\r\n",
    "            suf[i] = suf[i+1] | nums[i+1]\r\n",
    "        ans = 0\r\n",
    "        for i in range(n):\r\n",
    "            ans = max(ans, pre[i] | suf[i] | (nums[i] << k))\r\n",
    "        return ans\r\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
